/*
    created: 2023/4/28
    filename: Search.cpp
    author: 李东霖
    purpose: 查找算法
*/

#include"search.h"
//二分查找，只适用于有序数组  
int Search_Binary(ElemType arr[],size_t len,ElemType* val)
{
    if(len == 0) return -1;
    int low = 0;
    int high = len - 1; 
    while(low <= high)
    {
        int mid = (high-low)/2+low;
        if(arr[mid] == *val) return mid;
        //查找范围在左边
        if(arr[mid] > *val) high = mid  - 1;
        else low = mid + 1;
    }
    return -1;
}
//递归子函数
int S_B_R(ElemType arr[],size_t low,size_t high,ElemType* val)
{
    if(low > high) return -1;
    int mid = (high-low)/2+low;
    if(arr[mid] == *val) return mid;
    //查找范围在左边
    if(arr[mid] > *val) return S_B_R(arr,low,mid-1,val);
    else low = mid + 1; return S_B_R(arr,mid+1,high,val);
}
//二分查找的递归方案
int Search_Binary_R(ElemType arr[],size_t len,ElemType* val)
{
    if(len == 0) return -1;
    return S_B_R(arr,0,len-1,val);
}

